\documentclass[12pt]{exam}

\usepackage{gastex}
\usepackage{amsmath}
\usepackage{verbatim}
%\usepackage{graphicx}
\usepackage{timestamp} % http://brasserie-seul.com/?Recipes&nr=16

\addpoints

\renewcommand{\solutiontitle}{\noindent\textbf{Solution:}\par\noindent}

\begin{document}

\printanswers

\pagestyle{head}
\firstpageheader{CS 59000-009}{Exam}{Fall 2018}

% just in case we need an image file
%\includegraphics[width=2in]{problem.png}

The following questions ask you to analyze some code fragments and to write some code fragments. When you analyze some code, your analysis should be written in complete sentences organized into paragraphs. Do not write sentence fragments and do not write the most terse answer that you can think of (even if it is essentially correct). You are being graded on your ability to communicate, not just on your ability to arrive at correct solutions.

\bigskip

Write all your answers neatly using a computer document format. You can write your answers in a plain text file, a MS Word document, an HTML page, or even in \LaTeX. Put your exam, and any supporting files that you might like to submit (like compilable code), in a zip file and submit your zip file to me using Blackboard.

\bigskip

Each person should work on this exam by themself. If you have any questions about the exam, feel free to send me an e-mail.

\bigskip

This exam should be turned in to Blackboard by Friday, December 14.

\vspace*{\fill}
\newpage

\begin{questions}

\question
The following code outlines a synchronization pattern. Assume that the two threads begin at the same time, each thread runs on its own CPU core, and there are no other (significant) threads running on the cores.

\vspace{-.15truein}
\begin{verbatim}
void *thread1(void *vargp)
{  while(1)
   {  << do Calculation A >>
      sem_post(&semaphore1);
      << do Calculation B >>
      sem_post(&semaphore2);
      sem_wait(&semaphore3);
   }
}

void *thread2(void *vargp)
{  while(1)
   {  sem_wait(&semaphore1);
      << do Calculation C >>
      sem_post(&semaphore3);
      sem_wait(&semaphore2);
   }
}

sem_t semaphore1, semaphore2, semaphore3;

int main()
{  pthread_t tid;
   sem_init(&semaphore1, 0, 0); // not signaled
   sem_init(&semaphore2, 0, 0); // not signaled
   sem_init(&semaphore3, 0, 0); // not signaled
   pthread_create(&tid, NULL, thread1, NULL);
   pthread_create(&tid, NULL, thread2, NULL);
   while(1){ Sleep(1000); }
}
\end{verbatim}

\begin{parts}

\part[8]
In what way are the two threads synchronized? Give your answer in terms of how the three calculations, A, B, and C, are ordered in time. Explain what parts are sequential and what parts are in parallel. Explain carefully what role each of the three semaphores plays in the synchronization.

\begin{comment}
\begin{solution}
   % put your solution to problem 1a here
\end{solution}
\end{comment}

\vspace*{\fill}

\part[12]
Rewrite this program using condition variables.

\begin{comment}
\begin{solution}
   % put your solution to problem 1b here
\end{solution}
\end{comment}

\end{parts}


\vspace*{\fill}
\newpage


\question
Suppose that we have five C functions
\begin{comment}
\begin{verbatim}
   void functionA(void);
   void functionB(void);
   void functionC(void);
   void functionD(void);
   void functionE(void);
\end{verbatim}
\end{comment}
that together solve some problem. Suppose these functions, labeled {\tt A} through {\tt E}, depend on each other according to the following graph.

\smallskip
\unitlength=1cm
\begin{picture}(5,2.6)
\gasset{linewidth=0.05,AHLength=0.3,AHlength=0.282}
% states
\node(A)(4,2){$A$}
\node(B)(6,2){$B$}
\node(C)(8,2){$C$}
\node(D)(7,1){$D$}
\node(E)(5,0){$E$}
% transitions
\drawedge(A,E){}
\drawedge(B,D){}
\drawedge(C,D){}
\drawedge(D,E){}
\end{picture}

\smallskip
Each edge of the graph denotes a dependency between two of these functions. For example, the edge from node B to node D means that {\tt functionB} must be called, and must return, before {\tt functionD} can be called.

\begin{parts}
\part[8]
What is wrong with this sketch of a C program that uses Pthreads to execute the five functions in parallel in a way that adheres to the above dependency graph? How would you improve this program (but still use five worker threads and only the Pthreads functions {\tt pthread\_create()} and {\tt pthread\_join()})?
\smallskip
\begin{verbatim}
void *threadA(void *vargp){ functionA(); }
void *threadB(void *vargp){ functionB(); }
void *threadC(void *vargp){ functionC(); }
void *threadD(void *vargp){ functionD(); }
void *threadE(void *vargp){ functionE(); }
int main()
{  pthread_t tidA, tidB, tidC, tidD, tidE;
   pthread_create(&tidB, NULL, threadB, NULL);
   pthread_create(&tidC, NULL, threadC, NULL);
   pthread_join(tidB, NULL);
   pthread_join(tidC, NULL);
   pthread_create(&tidA, NULL, threadA, NULL);
   pthread_create(&tidD, NULL, threadD, NULL);
   pthread_join(tidA, NULL);
   pthread_join(tidD, NULL);
   pthread_create(&tidE, NULL, threadE, NULL);
   pthread_join(tidE, NULL);
}
\end{verbatim}

\begin{comment}
\begin{solution}
   % put your solution to problem 2a here
\end{solution}
\end{comment}


\vspace*{\fill}


\part[12]
Write another sketch of a Pthreads program to execute the above five functions in a way that is maximally parallel (i.e., always runs as many threads in parallel as possible), adheres to the above dependency graph, and uses the minimal number of threads possible (including the {\tt main()} thread!). Your solution should still use only {\tt pthread\_join()} for synchronization.

\begin{comment}
\begin{solution}
   % put your solution to problem 2b here
\end{solution}
\end{comment}

\end{parts}


\vspace*{\fill}
\newpage


\question[12]
Suppose that we have six C functions
\begin{verbatim}
   void functionA(void);   void functionD(void);
   void functionB(void);   void functionE(void);
   void functionC(void);   void functionF(void);
\end{verbatim}
that together solve some problem. Suppose these function depend on each other according to the following dependency graph.

%\smallskip
\unitlength=1cm
\begin{picture}(5,3.5)
\gasset{linewidth=0.05,AHLength=0.3,AHlength=0.282}
% states
\node(A)(4,3){$A$}
\node(B)(6,3){$B$}
\node(C)(8,3){$C$}
\node(D)(7,2){$D$}
\node(F)(4.5,1.5){$F$}
\node(E)(5,0){$E$}
% transitions
\drawedge(A,F){}
\drawedge(B,D){}
\drawedge(B,F){}
\drawedge(C,D){}
\drawedge(D,E){}
\drawedge(F,E){}
\end{picture}

\smallskip
Write a sketch of a C program that uses Pthreads to execute the above six functions in a way that is maximally parallel, but adheres to the above dependency graph. Give a written explanation of how your code solves the problem. You can use any synchronization mechanism you want (join, condition variables, semaphores, etc.).

\begin{comment}
\begin{solution}
   % put your solution to problem 3 here
\end{solution}
\end{comment}

\vspace*{\fill}
\newpage


\question[15]
This question is about I/O redirection and pipes on the Windows command-line. Explain what each of the following possible command-lines mean. In each part, you need to associate an appropriate meaning to the symbols {\tt a}, {\tt b} and {\tt c} (for example ``b names a program, a and c name files'' or ``a and b name programs and c is a parameter to b''). Also give an example of a runnable command-line with the given format (using programs like {\tt dir}, {\tt sort}, {\tt more}, etc.). You might find the following web pages useful.
\begin{verbatim}
http://ss64.com/nt/syntax-redirection.html
https://technet.microsoft.com/en-us/library/bb490954.aspx
\end{verbatim}

\begin{parts}
\part {\tt z:\char`\\> a > b < c}

\vspace*{\fill}

\part {\tt z:\char`\\> a | b > c}

\vspace*{\fill}

\part {\tt z:\char`\\> a < b | c}

\vspace*{\fill}

\part {\tt z:\char`\\> a < b \& c}

\vspace*{\fill}

\part {\tt z:\char`\\> a b | c}

\vspace*{\fill}

\part {\tt z:\char`\\> a \& b | c}

\vspace*{\fill}

\part {\tt z:\char`\\> a \& (b | c)}
\end{parts}


\vspace*{\fill}
\newpage


\question[8]
What problem is there with each of the following two command lines?
\begin{parts}
\part {\tt z:\char`\\> a | b < c}

\vspace*{\fill}

\part {\tt z:\char`\\> a > b | c}
\end{parts}


\vspace*{\fill}


\question[5]
Draw a picture illustrating the processes, streams, pipes, and files in this command-line.
\\ \texttt{z:\char`\\> a < b | c 2> d | e > f 2> d}


\vspace*{\fill}
\newpage


\question[10]
Draw a picture that illustrates all the processes, pipes, file descriptors, and (possibly shared) streams after the following code has executed.
\begin{verbatim}
int main() {
   int pipefd_1[2];
   int pipefd_2[2];
   pipe(pipefd_1);
   pipe(pipefd_2);

   int fork_rv1 = fork();
   if ( fork_rv1 > 0 ) {
      int fork_rv2 = fork();
      if ( fork_rv2 > 0 ) {
         close(4);
         close(5);
         dup(6);
         close(6);
         while(1)/* do work... */;
      } else {
         close(5);
         close(6);
         close(3);
         close(1);
         dup(4);
         close(4);
         while(1)/* do work... */;
      }
   } else {
      close(3);
      close(4);
      close(6);
      close(0);
      dup(5);
      close(5);
      while(1)/* do work... */;
   }
   return 0;
}
\end{verbatim}


\vspace*{\fill}
\newpage


\question[10]
Draw a picture that illustrates all the processes, pipes, file descriptors, and (possibly shared) streams after the following code has executed.
\begin{verbatim}
int main() {
   int pipefd_1[2];
   int pipefd_2[2];
   pipe(pipefd_1);
   pipe(pipefd_2);

   int fork_rv1 = fork();
   if ( fork_rv1 > 0 ) {
      int fork_rv2 = fork();
      if ( fork_rv2 > 0 ) {
         close(3);
         close(4);
         close(5);
         close(6);
         while(1)/* do work... */;
      } else {
         close(4);
         close(6);
         close(0);
         dup(3);
         close(3);
         dup(5);
         close(5);
         while(1)/* do work... */;
      }
   } else {
      close(3);
      close(5);
      close(1);
      dup(4);
      close(4);
      dup(6);
      close(6);
      while(1)/* do work... */;
   }
   return 0;
}
\end{verbatim}


\vspace*{\fill}

%Total of \numpoints\ points

\hfill\timestamp  % add a time stamp at lower right hand corner

\end{questions}

\end{document}
